The present invention relates to a congestion control method for use in a packet switch. More particularly, the present invention relates to a method and apparatus for controlling congestion in a packet switch based on a threshold value which indicates the amount of volume that causes congestion.
As a first conventional technique there is packet transferring technology known as Asynchronous Transfer Mode (ATM). The word "packet" referred to herein corresponds to a cell in the ATM. The ATM is also one example of packet switching technology in a broad sense. An ATM is disclosed, for example, in "Data Communication Using ATM: Architecture, Protocols, and Resource Management", IEEE Communication Magazine, August 1994, pp 24-31.
In an ATM connection information is set by a signalling process for a route which transfers each cell (or fixed-length packet). The route extends from a transmission source to a reception destination via switches. After completion of the signalling process, the cell is transferred on the route for which a connection has been set.
The connection information is stated in accordance with, for example, "Q.2931 3.Message function definitions and contents". Included in the connection information are identifiers which serve to identify the connection on each of the links between the transmission source and the switch, and between the switch and the reception destination; and traffic classes which indicate the priority levels of the cell transfer within the switches, etc. The identifiers are called the "VPI (Virtual Path Identifier)" and the "VCI (Virtual Connection Identifier)", and they become the address information of the header of the cell.
The transfer of the cell will be explained below. Upon receiving the cell, the switch reads out the connection information necessary for the cell transfer as set by the connection process based on the VPI and VCI of the received cell. The items of the necessary connection information are, for example, the number of an output port, an identifier at the time of output of the cell, and the traffic class indicative of the priority level of the cell within the switch.
Examples of different traffic classes are as follows: UBR (Unspecified Bit Rate) traffic class is a traffic class in which a network guarantees nothing as to the transfer of the cell. ABR (Available Bit Rate) traffic class is a traffic class in which a feedback control is performed as to a congested state between a network and a terminal so as to guarantee the prevention of cell loss. VBR (Variable Bit Rate) traffic class is a traffic in which the network allows for cells to be transferred at a rate that varies over time. CBR (Constant Bit Rate) traffic class is a traffic class in which a fixed amount of bandwidth is continuously made available by the network to transfer cells.
The ABR traffic class is disclosed in "The Rate-Based Flow Control Framework for the Available Bit Rate ATM Service", IEEE Network March/April 1995 pp 25-39, or in ATM JIG News Letter Vol.2, No.2, pp 2-3. As described in this reference in the ABR traffic class, a bandwidth management cell called the "RM (Resource Management) cell" is occasionally sent by the transmission terminal within the same connection as that of the data cell. The bandwidth management cell is returned to the terminal again via the switch within the network and a reception terminal. In this regard, when either of the network switch or the reception terminal is in the congested state, it writes congestion notification information into the bandwidth management cell. Thus, the transmission side terminal is accordingly notified of the congested state, and it suppresses the transmission rate thereof. Accordingly, the occurrence of cell discard within the network can be prevented.
FIG. 16 illustrates the control of the ABR traffic class which is the feedback-type congestion control. Within the identical connection, the congested-state notification cell (bandwidth management cell) is periodically transmitted every predetermined number of data cells. The bandwidth management cell is sent back to the transmission source terminal "A" 162 by the reception destination terminal "B" 164. The switch 100 or the reception destination terminal "B" 164 writes control information into the congestion notification indication 242 of the bandwidth management cell 240 based on its congested state as illustrated in FIG. 2B. The transmission source terminal "A" 162 having received the bandwidth management cell with the congestion notification indication 242 adjusts the transmission rate in accordance with the indication.
The congestion notification indication for the bandwidth management cell is divided into a binary marking mode wherein the transmission source terminal is notified of only the indication of increase or decrease in a bandwidth, and an explicit marking mode wherein the transmission source terminal is notified of an allowed transmission bandwidth.
The binary marking mode also includes a mode wherein the congestion notification indication is written into the data cell not the transmitted bandwidth management cell and the congestion notification indication is reflected in a bandwidth management cell to-be-looped-back in the reception side terminal.
A second conventional technique of a switch of the asynchronous transfer mode is disclosed in, for example, Japanese Patent Application Laid-open No. 197128/1994 entitled "Packet Switching Technology". According to the switch stated in "Packet Switching Technology", buffers such as RIRO type input buffers and FIFO type output buffers are included in the switch, and an input buffer control unit determines a cell which is to be delivered from the RIRO type input buffer in the next time slot, based on table information which indicates the empty state of the output buffer.
In the asynchronous transfer mode, a connection is first set, and a cell is thereafter sent out. An identifier for identifying communication in the identical connection is included in the header of the cell being transferred. The switch changes-over routes based on the identifier and information which has been set within the switch at the time of the setting of the connection.
In the second conventional technique a portion associated with output lines has the output buffers respectively disposed for two traffic classes namely CBR and VBR, and table information is held in order to indicate the empty states of the two buffers for each of output ports. A portion associated with input ports has the input buffers disposed respectively for the two traffic classes CBR and VBR, and respectively for the output ports of the class VBR. The output priority level of the CBR buffer is set higher than that of the VBR buffer, whereby the communication delay time of the traffic class CBR as is severely restricted is permitted to become shorter than a certain time. Further, in a case where the CBR buffer is full, the cell is transferred to the VBR buffer having an empty address (which is often existent ordinarily), whereby the effective utilization of the bandwidth of the switch is attained. Incidentally, the traffic classes ABR and UBR can be supported, for example, in such a way that output buffers corresponding to these traffic classes are disposed in addition to the output buffers of the traffic classes CBR and VBR in the switch of the known example.
A third conventional technique of a switch of the asynchronous transfer mode is disclosed in B-598 "Development of 622 Mbps 8.times.8 ATM Switch LSI having Delay Priority Control Function for 5 Classes", '96 National Meeting of the (Japan) Institute of Electronics, Information and Communication Engineers. The paper B-598 in the '96 National Meeting of the Institute of Electronics, Information and Communication Engineers discloses an architecture wherein a cell accumulating buffer common to a plurality of output ports is disposed instead of physically independent buffers for respective output ports. Further, the paper discloses a technique wherein information on a cell number counter for each traffic class and information on a threshold value for each traffic class are held within the switch. The notification of congestion is made when the value of the cell number counter has exceeded the threshold value.
The architecture of a fourth conventional technique of a switching system for handling ATM cells, in which a cell accumulating buffer common to a plurality of output ports is disposed in the same manner as in the third conventional technique is detailed in, for example, Japanese Patent Application Laid-open No. 276943/1992.
In the switching techniques described above as the second, third and fourth conventional techniques there is no disclosure concerning the cell transferring technique for the connection of the ABR traffic class referred to in the first conventional technique.
When an output port has fallen into a congested state, a switch detects the congested state, and it writes congestion notification information into a bandwidth management cell which is transferred on a connection made according to the ABR traffic class. In realizing a switch adapted to support the ABR traffic class, however, the capabilities of the traffic control (such as throughput, cell discard ratio, the number of supportable connections, a supportable transfer length, the fairness among connections, and securing the bandwidth of a designated connection) differ greatly depending upon methods which initiating the above operations in the switch. In turn, the initiating methods in the switch depend greatly upon a method for detecting the congested state, a connection selection method for selecting the notifying connection from among a plurality of connections, a generation method for generating the congestion notification information from detected congestion information, etc., so that these methods are important.
In the binary marking mode, it becomes important to initiate a fairness guaranteeing control in which the notifying connection is selected so that the respective transfer rates of the plurality of connections utilizing the ABR traffic class may become equal to one another even on the occasion of the congestion. Also initiated is a bandwidth securing control in which the connection is selected by weighting so that, contrary to the above, a bandwidth may be preferentially assigned to an appointed specific connection.